package com.ry.day1129;

import java.util.HashMap;
import java.util.Map;

public class LC1169 {

    static class Solution {
        /**
         * @param s1: a string
         * @param s2: a string
         * @return: if s2 contains the permutation of s1
         */
        public boolean checkInclusion(String s1, String s2) {
            //双指针
            Map<Character, Integer> s1map = new HashMap<>();
            Map<Character, Integer> s2map = new HashMap<>();
            for (int i = 0; i < s1.length(); i++) {
                char c = s1.charAt(i);
                if (!s1map.containsKey(c))
                    s1map.put(c, 0);

                s1map.put(c, s1map.get(c) + 1);
            }

            int end = 0;
            int n = s2.length();
            int macthed = 0;
            for (int start = 0; start < n; start++) {
                while (end < n && macthed < s1map.size()) {
                    char ch = s2.charAt(end);
                    if(!s2map.containsKey(ch))
                        s2map.put(ch,0);

                    s2map.put(ch,s2map.get(ch)+1);

                    if(s2map.containsKey(ch) && s2map.get(ch).equals(s1map.get(ch))){
                        macthed++;
                    }

                    end++;
                }

                if(macthed == s1map.size()){
                    if(end-start == s1.length()) return true;
                }

                char ch = s2.charAt(start);
                s2map.put(ch,s2map.get(ch)-1);

                if(s1map.containsKey(ch) && s2map.get(ch).equals(s1map.get(ch)-1)){
                    macthed--;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.checkInclusion("ab", "eidbaooo"));
        System.out.println(obj.checkInclusion("ab", "eidboooo"));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1169 · 字符串的排列
算法
中等
通过率
55%

题目
题解18
笔记
讨论32
排名
记录
描述
给定两个字符串s1和s2，如果s2包含s1的排列，则写一个函数返回true。 换句话说，第一个字符串的排列之一是第二个字符串的substring。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


输入的字符串只包含小写字母。
两个字符串的长度范围都为[1, 10,000]。
样例
样例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: true
解释: s2包含s1的一个排列("ba").
样例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: false
相关知识
学习《2024年4月北美大厂最新面试真题精讲》课程中的1.12Amazon：最新面试精选006相关内容 ，了解更多相关知识！
标签
企业
Microsoft
相关题目

32
最小子串覆盖
中等

647
子串字谜
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
12345678

    控制台
            历史提交

 */
